package leetcode.tree.binary.sort;


import cn.hutool.core.lang.Pair;

import java.util.HashMap;
import java.util.Map;


/**
 * 96. 不同的二叉搜索树
 *
 *
 * 求恰由 n个节点组成且节点值从 1到 n互不相同的 二叉搜索树的个数
 *
 */
public class NumTrees {

    public static void main(String[] args) {
        NumTrees solution = new NumTrees();
        int count = solution.numTrees(19);
        System.out.println(count);
    }

    /**
     * 递归回溯 + HashMap实现
     *
     * @param n 数字n
     * @return
     */
    public int numTrees(int n) {
        return treeNums(1, n);
    }

    public Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

    public int treeNums(int start, int end) {
        if (start > end) {
            return 1;
        }
        Pair<Integer, Integer> pair = new Pair<>(start, end);
        if (map.containsKey(pair)) {
            return map.get(pair);
        }

        int sum = 0;
        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            int left = treeNums(start, i - 1);
            // 获得所有可行的右子树集合
            int right = treeNums(i + 1, end);
            sum = sum + left * right;
        }
        map.put(new Pair<>(start, end), sum);
        return sum;
    }


    /**
     * 动态规划实现
     *
     *
     * 思路推导
     *      G(n)为 n个节点存在二叉排序树的个数, f(n)为 i为根的二叉搜索树的个数
     *      G(n) = f(1) + f(2) + f(n)
     *      f(i) = G(i−1) ∗ G(n−i)
     *      G(n) = G(0)∗G(n−1) + G(1)∗G(n−2) +...+ G(n−1)∗G(0)  卡特兰数公式
     *
     * @param n 数字n
     * @return
     */
    public int numTrees2(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n + 1; i++)
            for (int j = 1; j < i + 1; j++)
                dp[i] += dp[j - 1] * dp[i - j];

        return dp[n];
    }
}
